package leetcode;
/**
 * 455.分发饼干
 * 假设你是⼀位很棒的家⻓，想要给你的孩⼦们⼀些⼩饼⼲。但是，每个孩⼦最多只能给⼀块饼⼲。
 * 对每个孩⼦ i，都有⼀个胃⼝值 g[i]，这是能让孩⼦们满⾜胃⼝的饼⼲的最⼩尺⼨；并且每块饼⼲ j，都有⼀个尺⼨ s[j] 。
 * 如果 s[j] >= g[i]，我们可以将这个饼⼲ j 分配给孩⼦ i ，这个孩⼦会得到满⾜。你的⽬
 * 标是尽可能满⾜越多数量的孩⼦，并输出这个最⼤数值。
 *
 * 示例 1:
 * 输⼊: g = [1,2,3], s = [1,1]
 * 输出: 1
 * 解释:
 * 你有三个孩⼦和两块⼩饼⼲，3个孩⼦的胃⼝值分别是：1,2,3。
 * 虽然你有两块⼩饼⼲，由于他们的尺⼨都是1，你只能让胃⼝值是1的孩⼦满⾜。 所以你应该输出1。
 * 示例 2:
 * 输⼊: g = [1,2], s = [1,2,3]
 * 输出: 2
 * 解释:
 * 你有两个孩⼦和三块⼩饼⼲，2个孩⼦的胃⼝值分别是1,2。 你拥有的饼⼲数量和尺⼨都⾜以让所有孩⼦满⾜。
 * 所以你应该输出2.
 */
import java.util.*;
public class Num_455 {
    //贪心的思路：
    //为了满⾜更多的⼩孩，就不要造成饼⼲尺⼨的浪费。
    //⼤尺⼨的饼⼲既可以满⾜胃⼝⼤的孩⼦也可以满⾜胃⼝⼩的孩⼦，那么就应该优先满⾜胃⼝⼤的。
    //这⾥的局部最优就是⼤饼⼲喂给胃⼝⼤的，充分利⽤饼⼲尺⼨喂饱⼀个，全局最优就是喂饱尽可能多的⼩孩。
    public int findContentChildren(int[] g, int[] s) {
        //先给两个数组排序
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        //s[j]表示最大的饼干
        int j = s.length - 1;
        //先遍历孩子的胃口，由大到小
        for(int i = g.length - 1; i >= 0; i--){
            //先看有没有饼干
            if(j < 0){
                break;
            }
            //再比较当前孩子和当前饼干
            if(g[i] > s[j]){
                //当前孩子胃口 > 剩余的最大饼干
                continue;
            }else{
                //当前孩子胃口 <= 剩余的最大饼干
                count ++;
                j --;
            }
        }
        return count;
    }
}
